package com.hy.backtracking2;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class IsPalindrome {


    /**
     * 131.分割回文串
     * 力扣题目链接
     *
     * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
     *
     * 返回 s 所有可能的分割方案。
     *
     * 示例: 输入: "aab" 输出: [ ["aa","b"], ["a","a","b"] ]
     *
     * 思路
     * 关于本题，大家也可以看我在B站的视频讲解：131.分割回文串（B站视频）
     *
     * 本题这涉及到两个关键问题：
     *
     * 切割问题，有不同的切割方式
     * 判断回文
     * 相信这里不同的切割方式可以搞懵很多同学了。
     *
     * 这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯。
     *
     * 一些同学可能想不清楚 回溯究竟是如何切割字符串呢？
     *
     * 我们来分析一下切割，其实切割问题类似组合问题。
     *
     * 例如对于字符串abcdef：
     *
     * 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个.....。
     * 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段.....。
     *
     */



    List<List<String>> res = new ArrayList<>();
    Deque<String> deque = new LinkedList<>();


    public List<List<String>> palindrome (){
        String str = "aab";
        backTracking(str,0);
        return res;
    }

    public void backTracking(String str,int startIndex){
        if (startIndex >= str.length()){
            res.add(new ArrayList<>(deque));
            return;
        }
        for (int i = startIndex; i < str.length(); i++) {
            //如果是回文子串，则记录
            if (isPalindrome(str,startIndex,i)){
                String s = str.substring(startIndex,i+1);
                deque.offerLast(s);
            }else {
                continue;
            }
            //起始位置后移，保证不重复
            backTracking(str,i+1);
            deque.removeLast();
        }
    }

    // 判断  是否回文串
    public boolean isPalindrome(String str,int start,int end){
        for (int i = start,j = end; i < j ; i++,j--) {
            if (str.charAt(i) != str.charAt(end)){
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        IsPalindrome isPalindrome = new IsPalindrome();
        System.out.println("回文串的数据: "+isPalindrome.palindrome());
    }
}
